#include "QuickSort.h"
#include "my_lib.h"
#include <stdlib.h>


static int
Quick_sort__partition(int * array, int L, int R)
{
	int p = array[L];
	register int i = L, j = R;
	while (i <= j) {
		while (array[i] < p)
			++i;
		while (array[j] > p)
			--j;
		if (i < j) {
			swap_ints(&array[i], &array[j]);
			++i;
			--j;
		} else
			return j;
	}
	return j;
}

static void
Quick_sort__main(int *array, int left, int right)
{
	int m;

	if (left < right) {
		m = Quick_sort__partition(array, left, right);
		Quick_sort__main(array, left, m);
		Quick_sort__main(array, m+1, right);
	}
	return;
}

void
Quick_sort(int * array, int a_size)
{
	return Quick_sort__main(array, 0, a_size - 1);
}

static int
Quick_sort_rand__partition(int * array, int L, int R)
{
	int p = array[(rand() % (R-L)) + L];
	register int i = L, j = R;
	while (i <= j) {
		while (array[i] < p)
			++i;
		while (array[j] > p)
			--j;
		if (i < j) {
			swap_ints(&array[i], &array[j]);
			++i;
			--j;
		} else
			return j;
	}
	return j;
}

static void
Quick_sort_rand__main(int *array, int left, int right)
{
	int m;

	if (left < right) {
		m = Quick_sort_rand__partition(array, left, right);
		Quick_sort_rand__main(array, left, m);
		Quick_sort_rand__main(array, m+1, right);
	}
	return;
}

void
Quick_sort_rand(int * array, int a_size)
{
	return Quick_sort_rand__main(array, 0, a_size - 1);
}
